Третичная структура алгебраической байесовской сети (АБС) требуется для построения как случайного минимального графа смежности, так и всего множества минимальных графов смежности. Помимо этого она требуется для нахождения лучшей или оптимальной вторичной структуры для заданной первичной структуры АБС. Целью работы является формирование четко определенного понятия третичной структуры АБС и связанных с ней объектов на основе синтеза существующих подходов, а также исследование их свойств. Рассмотрены все существующие подходы к определению понятий«клика», «множество клик» и «граф клик», а также классификация клик максимального графа смежности. Построена единая терминологическая база для описания сопутствующих объектов, удовлетворяющая критериям неизбыточности и полноты систематизации. Третичная полиструктура определена как семейство графов, построенных над подмножествами множества сужений максимального графа смежности, ребра которых соответствуют тем или иным родственным отношениям, определенным в статье. Третичная структура определена как ориентированный граф, ребра которого проведены от родительских вершин к сыновьем, а вершинами являются сужения максимального графа смежности на веса ребер и вершин, а также на пустой вес (родительский граф над расширенным множеством значимых клик).
Роль третичной полиструктуры алгебраической байесовской сети (АБС) заметно возросла. Вводимая изначально в качестве вспомогательного объекта для построения вторичной структуры, третичная полиструктура нашла свое применение в анализе цикличности вторичной структуры без ее непосредственного построения и предполагается к использованию для глобального вывода в АБС. Цель работы — выделение (с последующей систематизацией и оценкой сложности) существующих алгоритмов построения элементов третичной полиструктуры из алгоритмов построения вторичной структуры. В работе рассмотрены существующие алгоритмы построения элементов третичной полиструктуры и оценено время их работы. Приводятся четыре алгоритма построения пустого графа над подмножествами значимых клик и два алгоритма построения родительского графа над множеством стереоклик.
Алгебраические байесовские сети (АБС) представляют собой логико-вероятностную графическую модель систем знаний с неопределенностью. Работа алгоритмов логико-вероятностного вывода АБС зависит от выбора вторичной структуры, обычно представляемой графом смежности. В частности, возможности применения указанных алгоритмов препятствуют циклы, содержащиеся в этих графах. Цель работы — исследовать циклы вторичной структуры и выявить необходимые и достаточные условия цикличности или ацикличности минимальных графов смежности. Замкнутый сверху граф клик определяется как граф клик с добавленным к нему корнем (пракликой), полусиблинговые циклы определены как циклы, состоящие из вассалов, небратские полусиблинговые циклы определены как полусиблинговые циклы, пересечение всех вассалов, входящих в которые, пусто. Сформулирована и доказана теорема о циклах, утверждающая, что необходимым и достаточным условием цикличности минимального графа смежности является существование небратских полусиблинговых циклов в какой-либо клике. Следствием из теоремы является то, что все минимальные графы смежности, построенные над данной первичной структурой АБС, являются либо циклическими, либо ациклическими одновременно
Третичная структура алгебраической байесовской сети (АБС), представляемая в виде графа клик, важна для построения и анализа вторичной структуры АБС, а также для анализа ее первичной структуры. В статье предложены два алгоритма построения третичной структуры: алгоритм построения графа клик при помощи потомков и алгоритм построения графа клик снизу—вверх, доказана их корректность и оценено время работы. Оба алгоритма по заданному набору максимальных фрагментов знаний строят два упорядоченных множества, содержащие множества вершин и множества сыновей каждой клики. Приведены примеры первичных структур АБС, на которых первый алгоритм работает быстрее второго и, наоборот, второй — быстрее первого. Также установлены существование и единственность третичной структуры АБС для каждой первичной структуры АБС.
Предложен новый терминологический поход для формализации работы с графами смежности, основанный на понятии торакса, обозначающего множество ребер. Предложена новая система уточненных понятий теории графов смежности: вес, сужение, жила, магистральная связность, минимальный граф смежности. Уточнены также понятие графа смежности и формулировка теоремы о множестве минимальных графов смежности. Сформулирована и доказана лемма о независимом пути, утверждающая, что из набора непересекающихся множеств ребер найдутся два таких, что магистральный путь между ними не пересекается ни с каким множеством из набора.
Алгебраические байесовские сети (АБС), представляющие собой логико-вероятностную графическую модель систем знаний с неопределенностью и позволяют работать в том числе с интервальными оценками вероятности. Работа алгоритмов АБС во многом опирается на вторичную структуру, представляемую графов смежности. Особую роль играет множество минимальных графов смежности, которое содержат наиболее «эффективные» вторичные структуры. Цель данной статьи — оценить мощность указанного множества. Введено понятие объема, характеризующее число вершин, входящих в компоненты связности строго сужения. Использование понятия объема позволила выразить коэффициент раздробленности клик — ее численную характеристику, через которую была выражена мощность множества минимальных графов смежности.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи самоуправляемых клик), а также два улучшения, каждое из которых реализуется в отдельном алгоритме; однако нет алгоритма, который бы реализовал оба улучшения. Цельюданной работы является создание такого алгоритма, который бы реализовывал одновременно ряд улучшений базового алгоритма, вследствие чего он был бы более эффективным, чем существующие.Такой алгоритм был предложен, его корректность доказана.
Алгебраические байесовские сети представляют собой логико-вероятностную графическую модель систем знаний с неопределенностью и позволяют работать в том числе с интервальными оценками вероятности. Существенной для их работы является вторичная структура, представляемая в виде графа смежности. Данная статья исследует ребра клик минимальных графов смежности для спецификации различных типов клик. В частности, было доказано, что у определенного класса клик, которые являются основными с точки зрения построения множества минимальных графов смежности, множество вершин совпадает с множеством концов особых ребер, вес которых совпадает с весом клики.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи само-управляемых клик), однако он может быть улучшен путем привлечения результатов активно разрабатывающейся теории глобальной структуры алгебраической байесовской сети. Целью данной работы является разработать улучшенную версию этого алгоритма за счет усовершенствованного построения множества вершин, входящих в клики: вместо полного перебора всех весов клик и вершин производить поиск для каждой клики ее потомков среди других клик. Предложенное улучшение легко в основу нового алгоритма построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников, корректность которого также была доказана.
Известен эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов знаний (при помощи самоуправляемых клик), однако этот алгоритм может быть улучшен путем привлечения разработанной теории глобальной структуры алгебраической байесовской сети. Цель работы — улучшить работу этого алгоритма за счет усовершенствованного построения владений (компонент связности строгих сужений) — ключевых объектов в построении данного множество: строить их не прямым поиском, а путем анализа пересечений множеств вершин детей соответствующих клик. Был предложен алгоритм, реализующий предложенные улучшения, и доказана его корректность.
Алгебраические байесовские сети представляют собой логико-вероятностную графическую модель систем знаний с неопределенностью и могут быть применимы в обработкестатистических данных и машинном обучении. Важную роль в их работе играет вторичная структура, представляемая в виде графа смежности. Данная статья вводит классификацию клик минимальных графов смежности в зависимости от числа их детей, а также числа вхождения в них числа особых ребер. Получено восемь различных типов клик, для которых были получены и обоснованыоценки числа зависимых от них компонент (феодов и жил).
1 - 11 из 11 результатов